#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
public:
    bool hasPathSum(TreeNode* root, int targetSum) 
    {
        if(root == nullptr)
        {
            return false;
        }
        stack<pair<TreeNode *, bool>> st;
        int sum = 0;
        st.push(make_pair(root, false));
        while(!st.empty())
        {
            auto node = st.top().first;
            auto visited = st.top().second;
            st.pop();
            if(visited)
            {
                sum -= node->val;
                continue;
            }
            sum += node->val;
            st.push(make_pair(node, true));
            if(node->right != nullptr)
            {
                st.push(make_pair(node->right, false));
            }
            if(node->left != nullptr)
            {
                st.push(make_pair(node->left, false));
            }
            if(node->left == nullptr && node->right == nullptr && sum == targetSum)
            {
                return true;
            }
        }
        return false;
    }
};

// 辅助函数：创建二叉树节点
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    Solution solution;
    
    cout << "=== LeetCode 112. 路径总和 测试案例 ===" << endl;
    
    // 测试案例1: 示例1 - [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    cout << "\n测试案例1: [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22" << endl;
    TreeNode* root1 = createNode(5);
    root1->left = createNode(4);
    root1->right = createNode(8);
    root1->left->left = createNode(11);
    root1->right->left = createNode(13);
    root1->right->right = createNode(4);
    root1->left->left->left = createNode(7);
    root1->left->left->right = createNode(2);
    root1->right->right->right = createNode(1);
    
    bool result1 = solution.hasPathSum(root1, 22);
    cout << "输入: [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22" << endl;
    cout << "输出: " << (result1 ? "true" : "false") << endl;
    cout << "期望: true (路径: 5->4->11->2 = 22)" << endl;
    
    // 测试案例2: 示例2 - [1,2,3], targetSum = 5
    cout << "\n测试案例2: [1,2,3], targetSum = 5" << endl;
    TreeNode* root2 = createNode(1);
    root2->left = createNode(2);
    root2->right = createNode(3);
    
    bool result2 = solution.hasPathSum(root2, 5);
    cout << "输入: [1,2,3], targetSum = 5" << endl;
    cout << "输出: " << (result2 ? "true" : "false") << endl;
    cout << "期望: false (没有路径和为5)" << endl;
    
    // 测试案例3: 示例3 - [], targetSum = 0
    cout << "\n测试案例3: [], targetSum = 0" << endl;
    TreeNode* root3 = nullptr;
    
    bool result3 = solution.hasPathSum(root3, 0);
    cout << "输入: [], targetSum = 0" << endl;
    cout << "输出: " << (result3 ? "true" : "false") << endl;
    cout << "期望: false (空树)" << endl;
    
    // 测试案例4: 只有一个节点 [1], targetSum = 1
    cout << "\n测试案例4: [1], targetSum = 1" << endl;
    TreeNode* root4 = createNode(1);
    
    bool result4 = solution.hasPathSum(root4, 1);
    cout << "输入: [1], targetSum = 1" << endl;
    cout << "输出: " << (result4 ? "true" : "false") << endl;
    cout << "期望: true (路径: 1 = 1)" << endl;
    
    // 测试案例5: 只有一个节点 [1], targetSum = 2
    cout << "\n测试案例5: [1], targetSum = 2" << endl;
    TreeNode* root5 = createNode(1);
    
    bool result5 = solution.hasPathSum(root5, 2);
    cout << "输入: [1], targetSum = 2" << endl;
    cout << "输出: " << (result5 ? "true" : "false") << endl;
    cout << "期望: false (路径: 1 ≠ 2)" << endl;
    
    // 测试案例6: 负数情况 [-3,9,-10,null,5], targetSum = -8
    cout << "\n测试案例6: [-3,9,-10,null,5], targetSum = -8" << endl;
    TreeNode* root6 = createNode(-3);
    root6->left = createNode(9);
    root6->right = createNode(-10);
    root6->left->right = createNode(5);
    
    bool result6 = solution.hasPathSum(root6, -8);
    cout << "输入: [-3,9,-10,null,5], targetSum = -8" << endl;
    cout << "输出: " << (result6 ? "true" : "false") << endl;
    cout << "期望: false (路径: -3+9+5=11, -3+-10=-13)" << endl;
    
    // 测试案例7: 负数情况 [-3,9,-10,null,5], targetSum = 11
    cout << "\n测试案例7: [-3,9,-10,null,5], targetSum = 11" << endl;
    TreeNode* root7 = createNode(-3);
    root7->left = createNode(9);
    root7->right = createNode(-10);
    root7->left->right = createNode(5);
    
    bool result7 = solution.hasPathSum(root7, 11);
    cout << "输入: [-3,9,-10,null,5], targetSum = 11" << endl;
    cout << "输出: " << (result7 ? "true" : "false") << endl;
    cout << "期望: true (路径: -3+9+5 = 11)" << endl;
    
    // 测试案例8: 只有左子树 [1,2,null,3], targetSum = 6
    cout << "\n测试案例8: [1,2,null,3], targetSum = 6" << endl;
    TreeNode* root8 = createNode(1);
    root8->left = createNode(2);
    root8->left->left = createNode(3);
    
    bool result8 = solution.hasPathSum(root8, 6);
    cout << "输入: [1,2,null,3], targetSum = 6" << endl;
    cout << "输出: " << (result8 ? "true" : "false") << endl;
    cout << "期望: true (路径: 1+2+3 = 6)" << endl;
    
    // 测试案例9: 多个路径 [1,2,3,4,5], targetSum = 8
    cout << "\n测试案例9: [1,2,3,4,5], targetSum = 8" << endl;
    TreeNode* root9 = createNode(1);
    root9->left = createNode(2);
    root9->right = createNode(3);
    root9->left->left = createNode(4);
    root9->left->right = createNode(5);
    
    bool result9 = solution.hasPathSum(root9, 8);
    cout << "输入: [1,2,3,4,5], targetSum = 8" << endl;
    cout << "输出: " << (result9 ? "true" : "false") << endl;
    cout << "期望: true (路径: 1+2+5 = 8)" << endl;
    
    // 释放内存
    deleteTree(root1);
    deleteTree(root2);
    // root3 已经是 nullptr，不需要释放
    deleteTree(root4);
    deleteTree(root5);
    deleteTree(root6);
    deleteTree(root7);
    deleteTree(root8);
    deleteTree(root9);
    
    cout << "\n=== 测试完成 ===" << endl;
    cout << "\n注意：如果输出结果与期望不符，可能是因为迭代实现中路径和的维护有问题" << endl;
    cout << "建议考虑使用递归方法或在栈中存储累计路径和" << endl;
    
    return 0;
}